package algorithm

import (
	"TODecider/src/structs"
	"TODecider/src/util"
	"time"
)

type Greedy struct{}

// Match By Greedy algorithm with O(N^2) time complexity
func (greedy *Greedy) Match(wbg structs.WBG) map[int]int {
	graph := wbg.Graph
	E := len(graph)
	res := make(map[int]int)
	val := 0.0
	visited := make([]bool, E)
	iteration = 0
	startTime := time.Now()
	for i := 0; i < E; i++ {
		minIdx, minVal := -1, 1.0
		for j := 0; j < E; j++ {
			iteration++
			if graph[i][j] < minVal && !visited[j] {
				minVal = graph[i][j]
				minIdx = j
			}
		}
		res[i] = minIdx
		visited[minIdx] = true
	}
	// execution time statistics
	duration := int(time.Since(startTime) / 1e6)
	// clean the result
	for i := 0; i < E; i++ {
		val -= graph[i][res[i]]
	}
	util.PrintTOEvaluation(res, val, iteration, duration)
	return res
}
